package extra;

public class Pattern {

   public static int naive(String pattern, String text) {
        int m = pattern.length();
        int n = text.length();
        int i = 0;
        int j = 0;
        int k;

        for (k = 0; k < n - m + 1; k++) {
            i = 0;
            j = k;

            while (i < m && pattern.charAt(i) == text.charAt(j)) {

                i++;
                j++;
            }
            if (i == m) {
                return k;
            }
        }

        return -1;
    }

    static int naive1(String pattern, String text) {
        int m = pattern.length();
        int n = text.length();
        int i = 0;
        int j = 0;
        while (i < m && j - i < n - m + 1) {
            if (pattern.charAt(i) == text.charAt(j)) {

                j++;
                i++;
            } else {
                // Sinon la fen�tre avance d'une position.
                // j retourne � la position � droite du d�but de la fen�tre
                // i retourne au d�but motif.
                j = j - i + 1;
                i = 0;
            }
        }
        if (i == m) // Occurrence trouv�e en position j-i
        {
            return j - i;
        } else // Aucune occurrence
        {
            return -1;
        }
    }

    static int morrisPratt(String pattern, String text) {
        int m = pattern.length();
        int n = text.length();
        int[] s = new int[m];
        int i;
        int j;

        s[0] = i = -1;
        for (j = 1; j < m; j++) {
            // Ici i = s[j-1]
            while (i >= 0 && pattern.charAt(i) != pattern.charAt(j - 1)) {
                i = s[i];
            }

            s[j] = ++i;
        }

        i = 0;
        j = 0;
        while (i < m && j < n) {
            if (pattern.charAt(i) == text.charAt(j)) {

                j++;
                i++;
            } else {
                if (i == 0) {
                    j++;
                } else {
                    i = s[i];
                }
            }
        }
        if (i == m) {
            return j - i;
        } else // Aucune occurrence
        {
            return -1;
        }
    }

    static int knuthMorrisPratt(String pattern, String text) {
        int m = pattern.length();// Longueur du motif
        int n = text.length();	// Longueur du texte
        int[] r = new int[m];	// Fonction de suppl�ance
        int i;			// Position dans le motif
        int j;			// Position dans le texte
        // Calcul de la fonction de suppl�ance r
        // Pour tout i > 0, r[i] est la longueur du bord maximal compatible
        // du prefixe de longueur i du motif.  Rappelons qu'un bord d'un
        // pr�fixe est compatible si son occurrence pr�fixe est suivie d'une
        // lettre diff�rente de la lettre qui suit le pr�fixe.
        r[0] = i = -1;
        for (j = 1; j < m; j++) {
            // Ici i = s[j-1]
            while (i >= 0 && pattern.charAt(i) != pattern.charAt(j - 1)) {
                i = r[i];
            }
            i++;
            // Ici i = s[j]
            if (pattern.charAt(i) != pattern.charAt(j)) {
                r[j] = i;
            } else {
                r[j] = r[i];
            }
        }
        // Recherche du motif
        i = 0;
        j = 0;
        while (i < m && j < n) {
            if (pattern.charAt(i) == text.charAt(j)) {
                // Si les deux caract�res co�ncident,
                // les deux curseurs avancent d'une position vers la droite.
                j++;
                i++;
            } else {
                // Version pr�c�dente
                // if (i == 0)
                //     j++;
                // La nouvelle version prend en compte l'absence de bord
                // compatible c'est-�-dire le cas r[i] == -1
                if (r[i] == -1) {
                    i = 0;
                    j++;
                } else {
                    i = r[i];
                }
            }
        }
        if (i == m) // Occurrence trouv�e en position j-i
        {
            return j - i;
        } else // Aucune occurrence
        {
            return -1;
        }
    }

    public static void main(String[] args) {
        String[] arg = new String[2];
        if (arg.length > 1) {
//            System.out.println(morrisPratt(args[0], args[1]));
//            System.out.println(knuthMorrisPratt(args[0], args[1]));
            arg[0] = "java";
            arg[1] = "rgb juui java llio";
            System.out.println(naive(arg[0], arg[1]));

        } else {

            System.out.println("Usage : pattern text");
        }
    }
}
